package com.hy.study.sort;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MegerSort {
    private static  int count=0;
    public static void main(String[] args) {
       // int arr[] = {8, 4, 5, 7, 1, 3, 5, 2};
        int arr[] = new int[8000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 800000);
        }
        //归并排序需要一个额外的数组
        int temp[]=new int[arr.length];
        long startTime = System.currentTimeMillis();
        System.out.println("-----------排序之前----------");
     //   System.out.println(Arrays.toString(arr));
        mergeSort(arr,0,arr.length-1,temp);
        long endTime = System.currentTimeMillis();
        System.out.println("-----------排序之之后----------");
     //   System.out.println(Arrays.toString(arr));
        System.out.println("---------总共耗时("+(endTime-startTime)/1000+"秒)");

    }

    public static  void mergeSort(int arr[] ,int left,int right,int temp[]){
        if(left<right){
            int mid=(left+right)/2;//中间的索引
            //向左边递归进行分解
            mergeSort(arr,left,mid,temp);
            //向右递归分解
            mergeSort(arr,mid+1,right,temp);
            //合并
            meger(arr,left,mid,right,temp);
        }
    }

    /**
     * 合并的方法
     *
     * @param arr   待排序的原始数据
     * @param left  左边有序序列的初始所以
     * @param mid   中间索引
     * @param right 右边索引
     * @param temp  做中转的数组
     */
    public static void meger(int arr[], int left, int mid, int right, int[] temp) {
       // System.out.println("第"+(++count)+"次合并");
        int i = left;//表示左边有序序列的初始索引
        int j = mid + 1;//右边有序序列的初始索引
        int t = 0;//temp 下标的索引
        //一、先把所有两边有序的数据按照规则填充到temp数组，直到左右两边有其中一边处理完成
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {// 如果左边有序序列的元素 将左边的copy 到数组中
                temp[t] = arr[i];
                t++;
                i++;
            }else {//将右边有序序列的元素填充到temp 数组中
                temp[t]=arr[j];
                j++;
                t++;
            }
        }
        //二、将还有剩余的数据依次全部填充到temp 中
        while (i<=mid){//左边的有序序列还有剩余元素  全部填充到temp
            temp[t]=arr[i];
            t++;
            i++;
        }
        while (j<=right){//将右边剩余的copy 到temp 中
            temp[t]=arr[j];
            t++;
            j++;
        }

        //将temp 重新copy 到arr
        //并不是每次都copy 8 个
        t=0;
        int tempLeft=left;
        while (tempLeft<=right){
            arr[tempLeft]=temp[t];
            tempLeft++;
            t++;
        }
    }
}
